4 I ELEMENTS OF THE THEORY OF SETS

(1.2.9) For subsets X, Y of a set E (with (J written for (JE)

C (X u Y) = (G X) n (G Y), C (x n Y> = (C X) u (C Y).

The relations X c Y, (J X => (J Y are equivalent; the relations X n Y = 0,
XcgY, YcgX are equivalent; the relations XuY = E, CXc:Yť
(J Y c X are equivalent. The union {x} u {y} is written {x, y] ; similarly,
{x}u{y} u {z} is written {x, y, z}; etc.

3. PRODUCT OF TWO SETS

To any two objects a, b corresponds a new object, their ordered pair
(#,6); the relation (a, b) = (#', b1) is equivalent to "a = a' and b = bf";
in particular, (a, b) = (b, a) if and only if a = b. The first (resp. second) element
of an ordered pair c = (a, b) is called the first (resp. second) projection of c
and written a = prx c (resp. b = pr2 c).

Given any two sets X, Y (distinct or not), there is a (unique) set the
elements of which are all ordered pairs (x, y) such that x eX and y e Y;
it is written X x Y and called the cartesian product (or simply product)
ofXandY.

To a relation R.(x, y) between x e X and y e Y is associated the property
R(prA z, pr2 z) of z e X x Y; the subset of X x Y consisting of the elements
for which this property is true is the set of all pairs (x, y) for which R(*, y)
is true; it is called the graph of the relation R. Any subset G of X x Y is
the graph of a relation, namely the relation (x, y) G G. If X' c X, Y' c: Y,
the graph of the relation " x e X' and y e Y' " is X' x Y'. For every x e X,
G(JC) is the set of all elements y E Y such that (x, y) e G, and for every
y e Y, G"1^) is the set of all elements x e X such that (x, y) e G; G(x) and
G""1^) are called the cross sections of G at x and y.

The following propositions follow at once from the definitions :

(1 .3.1) The relation X x Y = 0 is equivalent to " X = 0 or Y = 0."

(1.3.2) If X x Y 7* 0 (which means that both X and Y are nonempty),
the relation X' x Yr c X x Y is equivalent to

"X'cX and Y'cY."

(1.3.3) (X x Y) u (X' x Y) = (X u X') x Y.

(1.3.4) (X x Y) n (X' x Y') = (X n X') x (Y n Y').lation {x e X | P(;c)} = {x e X | Q(x)} is equivalent